Parallel reversal schedules describe how to calculate the states of an evolutionary system, such as atmospheric and oceanographic simulations, in reverse order without having to keep all states in memory. This is possible without any increase in computation time, by recalculating intermediate results using multiple processors on a parallel computer system. These schedules are not only applied physical simulations that need to run in reverse, but also in algorithmic differentiation, which in turn is used, among others, in nonlinear optimization and to solve partial differential equations. Earlier research led to optimal schedules under the central assumption that if k states can be kept in memory, there are enough processors to run computations on roughly half of them in parallel, while the other half can only be used for holding checkpoints.
This diploma thesis is an attempt to continue the research by relaxing the central assumption, such that memory for a large number of plain checkpoints can be used with a comparatively small number of processors. To cope with this challenge, a symbolic approach to reversal schedules is proposed, and a comprehensive algebra is developed to analyze schedules via their profiles. This algebra is very generic and could have applications outside parallel reversal schedules. Using that instrument, new optimal schedules are developed, to be applied in situations where the earlier schedules are not applicable. Moreover, suboptimal schedules are provided where optimal schedules could not be found in a systematic way.